#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/19 17:52
# ===========================================
#       题目名称： 57. 插入区间
#       题目地址： https://leetcode.cn/problems/insert-interval/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import List


class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # 1. 判断intervals 或者 newInerval 两个中任意一个为空
        if not (intervals and newInterval):
            return intervals if intervals else [newInterval, ]
        # 2. 判断newInterval已经包含在里面
        if newInterval in intervals:
            return intervals
        # 3. 合并
        intervals.append(newInterval)
        # 4. 先对intervals的第二个元素进行排序
        intervals = sorted(intervals, key=lambda x: x[1])
        # 5. 去重
        if len(intervals) > 1:
            cur_index = 1
            while cur_index < len(intervals):
                if intervals[cur_index] == intervals[cur_index - 1]:
                    del intervals[cur_index]
                else:
                    cur_index += 1
        # 6. 合并
        merges = []
        while intervals:
            target = intervals.pop()  # 目标元素
            cur_index = len(intervals) - 1  # 当前下标
            while cur_index > -1:
                source = intervals[cur_index]
                if target[0] > source[1]:
                    break
                target = [min(source[0], target[0]), max(source[1], target[1])]
                del intervals[cur_index]
                cur_index -= 1
            merges.append(target)
        merges = sorted(merges, key=lambda x: x[0])
        return merges




if __name__ == '__main__':
    s = Solution()
    # [[1,5],[6,9]]
    print(s.insert(intervals=[[1, 3], [6, 9]], newInterval=[2, 5]))
    # [[1,2],[3,10],[12,16]]
    print(s.insert(intervals=[[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval=[4, 8]))
    # [[5,7]]
    print(s.insert(intervals=[], newInterval=[5, 7]))
    # [[1,5]]
    print(s.insert(intervals=[[1, 5]], newInterval=[2, 3]))
    # [[1,7]]
    print(s.insert(intervals=[[1, 5]], newInterval=[2, 7]))
